package algorithm.variousAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: LexicalOrder
 * @Description 386. 字典序排数
 * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
 *
 * 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
 * @Author skywingking
 * @Date 2022/4/18 22:33
 **/
public class LexicalOrder {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ret = new ArrayList<>();
        int number = 1;
        for(int i = 0; i < n; i++){
            ret.add(number);
            if(number * 10 <= n){
                number *= 10;
            }else{
                while(number % 10 == 9 || number + 1 > n){
                    number /= 10;
                }
                number++;
            }
        }
        return ret;
    }
}